package Q372;

/**
 * 超级次方
 *
 * @author 23737
 * @time 2021.12.5
 */
public class Test {

    public static void main(String[] args) {
        System.out.println(new Solution().superPow(2, new int[]{1, 0}));
        System.out.println(new Solution2().superPow(2, new int[]{1, 0}));
    }
}


/**
 * java快速幂
 */
class Solution {
    public static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        int res = 1;
        for (int i = 0; i < b.length; i++) {
            res = (int) ((long) res * pow(a, b[i]) % MOD);
            a = pow(a, 10);
        }
        return res;
    }

    private int pow(int a, int i) {
        if (i == 1) return a;
        if (i == 0) return 1;
        if (i == -1) return 1 / a;
        int half = pow(a, i / 2);
        int res = pow(a, i % 2);
        return half * half * res;
    }
}

class Solution2 {
    static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        int ans = 1;
        for (int i = b.length - 1; i >= 0; --i) {
            ans = (int) ((long) ans * pow(a, b[i]) % MOD);
            a = pow(a, 10);
        }
        return ans;
    }

    public int pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}
